package LeetCode;

public class LC_124_BinaryTreeMaximumPathSum {
    public static void main(String[] args) {

    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    static class Solution {
        int maxSum = Integer.MIN_VALUE;

        public int maxPathSum(TreeNode root) {
            if (root == null) return 0;
            getMaxSumWithCurNode(root);
            return maxSum;
        }

        int getMaxSumWithCurNode(TreeNode curNode) {
            int lmax = 0, rmax = 0;
            int value = curNode.val;
            if (curNode.left != null) lmax = getMaxSumWithCurNode(curNode.left);
            if (curNode.right != null) rmax = getMaxSumWithCurNode(curNode.right);
            value = value + (lmax > 0 ? lmax : 0) + (rmax > 0 ? rmax : 0);
            if (value > maxSum) maxSum = value;
            return curNode.val + Math.max(lmax > 0 ? lmax : 0, rmax > 0 ? rmax : 0);
        }
    }
}
